import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int[] arr = {1000000000,1000000000,1000000000,1000000000};
        List<List<Integer>> a = fourSum(arr,-294967296);
        System.out.println(a);
    }

    //四数之和
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        //给数组排序
        Arrays.sort(nums);

        List<List<Integer>> tmp = new ArrayList<>();
        //固定第一个数
        int fix1 = 0;
        int n = nums.length;
        while (fix1 <= n-4){

            //在后面的数组中找三数之和为target-nums[fix1]的组合
            //在后面的数组中再固定一个数
            int fix2 = fix1+1;


            //找三个正确的数
            while (fix2 <= n-3){
                //在后面的数组中找两数之和为target-nums[fix1]-nums[fix2]的组合
                //在后面的数组中定义left right双指针
                int left = fix2+1;
                int right = n-1;

                //找两个数
                while (left < right){
                    long sum = (long)nums[left]+(long)nums[right]+(long)nums[fix1]+(long)nums[fix2];
                    System.out.println(sum);
                    if (left<right && sum == target){
                        tmp.add(new ArrayList<Integer>(Arrays.asList(nums[fix1],nums[fix2],nums[left],nums[right])));
                        left++;
                        right--;
                        //将left 和 right移动到和之前不相等的位置
                        while (left<right && nums[left] == nums[left-1]){
                            left++;
                        }
                        while (left<right && nums[right] == nums[right+1]){
                            right--;
                        }
                    }else if (left<right && nums[left]+nums[right] > target-nums[fix1]-nums[fix2]){
                        //后面的两数之和大于第二个固定的数
                        right--;
                    }else {
                        //后面的两数之和小于第二个固定的数
                        left++;
                    }
                }
                //找完两个数之后，固定下一个fix2
                fix2++;
                while (fix2<n && nums[fix2]==nums[fix2-1]){
                    fix2++;
                }


            }

            //找完三个正确的数后，固定下一个fix1
            fix1++;
            while (fix1<n && nums[fix1] == nums[fix1-1]){
                fix1++;
            }




        }

        return tmp;




    }






//三数之和
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> tmp = new ArrayList<>();
        //排序
        Arrays.sort(nums);

        int fix = 0;
        while (fix<=nums.length-3){
            int left = fix+1;
            int right = nums.length-1;
            while (left < right){
                if (nums[fix]+ nums[left]+nums[right] == 0){

                    tmp.add(new ArrayList<Integer>(Arrays.asList(nums[fix],nums[left],nums[right])));
                    //判断right 和 left的应该移动到哪里
                    while (left<right && nums[right-1] == nums[right]){
                        right--;
                    }
                    right--;
                    while (left<right && nums[left+1] == nums[left]){
                        left++;
                    }
                    left++;

                }else if(nums[fix]+ nums[left]+nums[right] > 0){
                    right--;
                }else {
                    left++;
                }
            }
            while (fix<=nums.length-3 &&nums[fix+1] == nums[fix]){
                fix++;
            }
            fix++;


        }
        return tmp;

    }


    public int[] twoSum(int[] nums, int target) {
        int fix = 0;
        while(fix<nums.length && nums[fix]<=target){
            fix++;
        }
        int left = 0;
        int right = fix-1;
        while (left<right){
            if (nums[left]+nums[right]>target){
                right--;
            }else if(nums[left]+nums[right]<target){
                left++;
            }else{
                break;
            }
        }
        int[] a = {nums[left],nums[right]};
        return a;
    }














    public static int triangleNumber(int[] nums) {


        //排序
//        for(int i = 0;i<nums.length;i++){
//            int flag = 0;
//            for(int j = 0;j<nums.length-1-i;j++){
//                if (nums[j]>nums[j+1]){
//                    int tmp = nums[j];
//                    nums[j] = nums[j+1];
//                    nums[j+1] = tmp;
//                    flag = 1;
//                }
//            }
//            if (flag == 0){
//                break;
//            }
//        }

        Arrays.sort(nums);


        int left = 0;
        int right = nums.length-2;
        int fix = nums.length-1;
        int count = 0;
        while (fix>=2){
            while (left<right){
                if (nums[left]+nums[right]>nums[fix]){
                    count += (right-left);
                    right--;
                    left = 0;
                }else {
                    left++;
                }
            }
            fix--;
            right=fix-1;
            left=0;
        }

        return count;



    }

    private static boolean isTri(int left, int right, int fix, int[] nums) {
        if (nums[left]+nums[right]>nums[fix]){
            return true;
        }
        return false;

    }


    public static void main8(String[] args) {
        int[] nums = {4,2,3,4};
        System.out.println(triangleNumber(nums));
    }







    public static int maxArea(int[] height) {
       int max = 0;
       for(int i=0;i<height.length;i++){
           for(int j = i+1;j<height.length;j++){
               int h = height[i]<height[j]?height[i]:height[j];
               int v = (j-i)*h;
               if (v>max){
                   max=v;
               }
           }
       }
       return max;

    }

    public static int maxArea1(int[] height) {
        int left = 0;
        int right = height.length-1;
        int h = height[left]<height[right]?height[left]:height[right];
        int w = right-left;
        int max = h*w;
        while (left<right){
            if (height[left]<height[right]){
                left++;
            }else {
                right--;
            }
            h = height[left]<height[right]?height[left]:height[right];
            w = right-left;
            if (max<h*w){
                max = h*w;
            }

        }
        return max;

    }

    public static void main3(String[] args) {
        int[] arr = {1,8,6,2,5,4,8,3,7};
        System.out.println(maxArea(arr));
    }




    public int bitSum(int n){
        int sum = 0;
        while (n!=0){
            int t = n%10;
            sum += t*t;
            n/=10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n,fast = bitSum(n);
        while (slow!=fast) {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        if (slow==1){
            return true;
        }
        return false;
    }

    public void duplicateZeros(int[] arr) {
        int cur = 0;
        int dest = -1;
        while (dest<=arr.length){
            if (arr[cur]!=0){
                dest++;
                cur++;
            }else {
                dest += 2;
                cur++;
            }
        }
        if (dest>arr.length){
            dest--;
            arr[dest] = 0;
            dest--;
            cur--;
        }
        while (cur>=0){
            if (arr[cur]!=0){
                arr[dest] = arr[cur];
                dest--;
                cur--;
            }else {
                arr[dest] = 0;
                dest--;
                arr[dest] = 0;
                dest--;
                cur--;
            }
        }

    }


    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            char[] tmp = new char[101];
            int j = 0;
            for (int i = 0; i < str.length(); i++) {
                while (!have(str.charAt(i), tmp)) {
                    tmp[j] = str.charAt(i);
                    j++;
                }
            }
            for(int i=0;i<j;i++){
                System.out.print(tmp[i]);
                System.out.println();
            }
        }
    }
    public static boolean have(char a, char[] tmp) {
        for (int i = 0; i < tmp.length; i++) {
            if (tmp[i] == a) {
                return true;
            }
        }
        return false;
    }


//    public static void main1(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        while (in.hasNext()) { // 注意 while 处理多个 case
//            String str = in.next();
//            StringBuilder tmp = new StringBuilder();
//            int j = 0;
//            for(int i = 0;i<str.length();i++){
//                String a = String.valueOf(str.charAt(i));
//                while(tmp.indexOf(a)==-1){
//                    tmp.append(a);
//                    j++;
//                }
//            }
//            System.out.println(tmp);
//        }
//    }

}

